package com.zjj.learn.algorithmPlus.segment1.priorityQueue;

import com.zjj.learn.algorithmPlus.segment1.queue.Queue;

/**
 * 优先级队列添加数据和普通队列没有区别，但是在获取数据时就不是获取队列头部的数据了，而是获取优先级最高的数据。
 * <p>
 * 基于无序数组实现优先级队列
 * 使用无序数组，在添加数据时比较方便。但是在获取数据时复杂一些。
 *
 * @author zjj_admin
 */
public class ArrayPriorityQueue1<E extends Priority> implements Queue<E> {


    private final Priority[] array;
    private int size;

    public ArrayPriorityQueue1(int capacity) {
        size = 0;
        array = new Priority[capacity];
    }

    /**
     * 添加数据
     *
     * @param value 添加数据
     * @return
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        //向数组的尾部添加一个数据即可
        array[size] = value;
        size++;
        return true;
    }


    /**
     * 移除并返回优先级最高的一个数据
     *
     * @return
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //获取优先级最大的元素下标
        int max = selectMaxPriority();
        @SuppressWarnings("all")
        E value = (E) array[max];
        //从索引 max + 1 开始，将后面的数据整体向前移动 1 位
        System.arraycopy(array, max + 1, array, max, size - max - 1);
        size--;
        return value;
    }

    /**
     * 获取优先级最大的元素下标
     *
     * @return
     */
    private int selectMaxPriority() {
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 1; i < size; i++) {
            int priority = array[i].priority();
            if (priority > max) {
                max = priority;
                maxIndex = i;
            }
        }
        return maxIndex;
    }


    /**
     * 返回优先级最高的一个数据
     *
     * @return
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //获取优先级最大的元素下标
        int max = selectMaxPriority();
        @SuppressWarnings("all")
        E value = (E) array[max];
        return value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }
}
